package algorithm;


/**
 * @Author Antony
 * @Since 2018/11/15 14:39
 */
public class EightQueens {

    public static void main(String[] args) {
//        int[][] cheese = new int[4][4];
//        cheese[0] = new int[]{0,0,0,0};
//        cheese[1] = new int[]{0,0,1,0};
//        cheese[2] = new int[]{0,1,0,0};
//        cheese[3] = new int[]{0,0,0,0};
//
//        System.out.println(checkPosition(cheese, 3,3));

        System.out.println(eightQueens());
    }

    /**
     * 由于棋盘是对称的，那么只要找出以前4个为首的结果数，翻倍即是最后结果。
     * @return
     */

    public static int result = 0;
    public static int eightQueens(){
        long start = System.currentTimeMillis();
        int[][] cheese = new int[8][8];
        for(int i=0; i<4; i++){
            backtrack(cheese, i, 0);
        }
        result *=2;
        long end = System.currentTimeMillis();
        System.out.println("耗时---"+(end-start) + "ms");
        return result;
    }


    private static void backtrack(int[][] cheese, int x, int y){
        cheese[y][x] = 1;
        if(y == cheese.length-1){
            result++;
        }else{
            for(int i=0; i<cheese[0].length; i++){
                if(checkPosition(cheese,y+1,i)){
                    backtrack(cheese, i, y+1);
                }
            }
        }
        cheese[y][x] = 0;
    }

    /**
     * 校验位置是否可以放置
     * @param cheese
     * @param y
     * @param x
     * @return
     */
    private static boolean checkPosition(int[][] cheese, int y, int x){
        int left=x, right=x;
        int len = cheese[0].length;
        boolean leftCheck, rightCheck, upCheck, result;
        for(int i=y-1; i>=0; i--){
            left -= 1;
            right +=1;
            leftCheck = left<0 ? true : cheese[i][left]==0;
            rightCheck = right>=len ? true : cheese[i][right]==0;
            upCheck = cheese[i][x]==0;
            result = leftCheck && rightCheck && upCheck;
            if(!result){
                return false;
            }
        }
        return true;
    }
}
